package algorithm;

import algorithm.bean.RiverStatus;

import java.util.*;

/**
 * 渡河算法主体
 * @author letere
 * @since  2020-12-30 10:17
 */
public class CrossRiverAlg {
    /**
     * 船限载人数
     */
    private final int boat;
    /**
     * 渡河方式
     */
    private final List<List<String>> crossRiverWays;
    /**
     * 两岸状态
     */
    private final RiverStatus riverStatus;

    public CrossRiverAlg(int missionary, int savage, int boat) {
        this.boat = boat;
        riverStatus = new RiverStatus(missionary, savage, 0, 0, 1);
        crossRiverWays = new ArrayList<>(16);
    }

    /**
     * 执行算法
     */
    public void execute() {
        List<String> operations = new ArrayList<>(16);
        List<RiverStatus> history = new ArrayList<>(16);
        history.add(riverStatus);
        this.recursionCrossRiver(riverStatus, history, operations);
        // 打印渡河方案
        if (crossRiverWays.size() == 0) {
            System.out.println("无可行的渡河方法");
            return;
        }
        int index = 1;
        for (List<String> crossRiverWay : crossRiverWays) {
            System.out.printf("第%d种渡河方法：\n", index++);
            for (String operation : crossRiverWay) {
                System.out.println(operation);
            }
            System.out.println();
        }
    }

    /**
     * 递归渡河
     * @param riverStatus 两岸状态
     * @param history 两岸状态历史数据
     * @param operations 操作信息
     */
    private void recursionCrossRiver(RiverStatus riverStatus, List<RiverStatus> history, List<String> operations) {
        // 判断是否被吃
        if (isEat(riverStatus)) {
            return;
        }
        // 判断重复操作
        if (isRepeat(riverStatus, history)) {
            return;
        }
        // 判断是否完成（完成则记录操作方案）
        if (isFinish(riverStatus)) {
            List<String> riverWay = Arrays.asList(new String[operations.size()]);
            Collections.copy(riverWay, operations);
            crossRiverWays.add(riverWay);
            return;
        }
        // 获取渡河方法
        List<String> crossMethods;
        if (Objects.equals(riverStatus.getBoat(), 1)) {
            crossMethods = getCrossMethods(riverStatus.getMissionaryLeft(), riverStatus.getSavageLeft());
        } else {
            crossMethods = getCrossMethods(riverStatus.getMissionaryRight(), riverStatus.getSavageRight());
        }
        // 无可行的渡河方法（结束递归）
        if (crossMethods.size() == 0) {
            return;
        }
        // 递归遍历渡河方法
        String operation = "";
        RiverStatus currentState;
        for (String crossMethod : crossMethods) {
            // 按空格切割字符串，s[0]为传教士数，s[1]为野人数
            String[] s = crossMethod.split(" ");
            // 渡河
            currentState = copyRiverStatus(riverStatus);
            operation = crossRiver(currentState, Integer.parseInt(s[0]), Integer.parseInt(s[1]));
            operations.add(operation);
            history.add(currentState);
            // 递归渡河
            this.recursionCrossRiver(currentState, history, operations);
            // 递归回溯清除数据
            operations.remove(operations.size() - 1);
            history.remove(history.size() - 1);
        }
    }

    /**
     * 计算渡河方法
     * @return crossMethods
     */
    private List<String> getCrossMethods(int missionarySize, int savageSize) {
        // 初始化数据，将传教士人数/野人数将为传的大小
        missionarySize = Math.min(missionarySize, boat);
        savageSize = Math.min(savageSize, boat);
        // 计算可行的渡河方法(全野人 | 全传教士 | 传教士>=野人)
        List<String> crossMethods = new ArrayList<>(16);
        for (int i=1; i<=savageSize; i++) {
            crossMethods.add(0 + " " + i);
        }
        for (int i=1; i<=missionarySize; i++) {
            crossMethods.add(i + " " + 0);
        }
        for (int i=1; i<=savageSize; i++) {
            for (int j=i; j<=Math.min(missionarySize, boat-i); j++) {
                crossMethods.add(j + " " + i);
            }
        }
        return crossMethods;
    }

    /**
     * 渡河，并返回渡河操作信息
     * @param riverStatus 两岸状态
     * @param missionary 运送传教士数
     * @param savage 运送野人数
     * @return 操作信息
     */
    private String crossRiver(RiverStatus riverStatus, int missionary, int savage) {
        // 初始状态信息（记录操作）
        String startState = riverStatus.toString();
        // 以船在左岸为基准，右移为正，左移为负
        int direction = riverStatus.getBoat();
        // 修改传教士数
        if (missionary > 0) {
            riverStatus.setMissionaryLeft(riverStatus.getMissionaryLeft() - missionary * direction);
            riverStatus.setMissionaryRight(riverStatus.getMissionaryRight() + missionary * direction);
        }
        // 修改野人数
        if (savage > 0) {
            riverStatus.setSavageLeft(riverStatus.getSavageLeft() - savage * direction);
            riverStatus.setSavageRight(riverStatus.getSavageRight() + savage * direction);
        }
        // 修改船方向
        riverStatus.setBoat(-riverStatus.getBoat());
        // 结束状态信息（记录操作）
        String endState = riverStatus.toString();
        // 返回操作信息
        String operation = "";
        if (riverStatus.getBoat() == 1) {
            operation = String.format(" <---（传%d, 野%d）---- ", missionary, savage);
            return endState + operation + startState;
        } else {
            operation = String.format(" ----（传%d, 野%d）---> ", missionary, savage);
            return startState + operation + endState;
        }
    }

    /**
     * 复制对象（对象作为参数是地址引用，修改对象时最好复制一份，方便还原）
     * @param riverStatus 两岸状态
     * @return riverStatus
     */
    private RiverStatus copyRiverStatus(RiverStatus riverStatus) {
        return new RiverStatus(
                riverStatus.getMissionaryLeft(),
                riverStatus.getSavageLeft(),
                riverStatus.getMissionaryRight(),
                riverStatus.getSavageRight(),
                riverStatus.getBoat()
        );
    }

    /**
     * 判断是否发生吃人
     * @param riverStatus 两岸状态
     * @return true/false
     */
    private boolean isEat(RiverStatus riverStatus) {
        //判断左岸
        if (riverStatus.getMissionaryLeft() < riverStatus.getSavageLeft() && riverStatus.getMissionaryLeft() != 0) {
            return true;
        }
        //判断右岸
        if (riverStatus.getMissionaryRight() < riverStatus.getSavageRight() && riverStatus.getMissionaryRight() != 0) {
            return true;
        }
        return false;
    }

    /**
     * 判断是否重复操作（即：左向右传2野人， 右向左也传2野人，死循环）
     * @param riverStatus 两岸状态
     * @param history    历史数据
     * @return true/false
     */
    private boolean isRepeat(RiverStatus riverStatus, List<RiverStatus> history) {
        //遍历历史数据，查看是否有重复数据，有重复数据表明循环回原点，结束递归
        for (int i = 0; i < history.size() - 1; i++) {
            if (riverStatus.getMissionaryLeft() == history.get(i).getMissionaryLeft()
                    && riverStatus.getSavageLeft() == history.get(i).getSavageLeft()) {
                if (riverStatus.getBoat() == history.get(i).getBoat()) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 判断是否达成目标
     * @param riverStatus 两岸状态
     * @return true/false
     */
    private boolean isFinish(RiverStatus riverStatus) {
        return riverStatus.getMissionaryLeft() == 0
                && riverStatus.getSavageLeft() == 0
                && riverStatus.getBoat() == -1;
    }
}
